﻿// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

class DeviceList {
public:
    DeviceList():ParentID(""), DeviceID(""), level(-1) {};
    ~DeviceList() {};
public:
    string ParentID;
    string DeviceID;
    int level;
};

int main()
{
    vector<DeviceList> vecDeviceList;

    DeviceList tDeviceList;
    tDeviceList.ParentID = "10001";
    tDeviceList.DeviceID = "100011";
    vecDeviceList.push_back(tDeviceList);

    tDeviceList.ParentID = "10001";
    tDeviceList.DeviceID = "100012";
    vecDeviceList.push_back(tDeviceList);

    tDeviceList.ParentID = "100011";
    tDeviceList.DeviceID = "1000111";
    vecDeviceList.push_back(tDeviceList);

	tDeviceList.ParentID = "100012";
	tDeviceList.DeviceID = "1000121";
	vecDeviceList.push_back(tDeviceList);

    tDeviceList.ParentID = "1000111";
    tDeviceList.DeviceID = "10001111";
    vecDeviceList.push_back(tDeviceList);

	tDeviceList.ParentID = "1000121";
	tDeviceList.DeviceID = "10001211";
	vecDeviceList.push_back(tDeviceList);

	tDeviceList.ParentID = "10001211";
	tDeviceList.DeviceID = "100012111";
	vecDeviceList.push_back(tDeviceList);


	map<string,int> mapParentIDList;
    set<string> setDeviceList;
	for (int i = 0;i < vecDeviceList.size();i++)
	{
        mapParentIDList[vecDeviceList[i].ParentID] = -1;
		setDeviceList.insert(vecDeviceList[i].DeviceID);
	}

    map<string, int>::iterator iter;
    set<string>::iterator iter_1;
	for (iter= mapParentIDList.begin();iter!= mapParentIDList.end();iter++)
	{
        iter_1 = setDeviceList.find(iter->first);
        if (iter_1 == setDeviceList.end())
        {
            //根目录
            cout << "迭代器指向: " << iter->first << endl;
            for (int i = 0;i < vecDeviceList.size();i++)
            {
                if (0 == strncmp(vecDeviceList[i].ParentID.c_str(), iter->first.c_str(), vecDeviceList[i].ParentID.length()))
                {
                    vecDeviceList[i].level = 0;
                    iter->second = 0;
                }
            }
        }
	}

	for (int i = 0;i < vecDeviceList.size();i++)
	{
		printf("%d %s %s\n", vecDeviceList[i].level,
			vecDeviceList[i].ParentID.c_str(),
			vecDeviceList[i].DeviceID.c_str());
	}

	for (int i = 0;i < vecDeviceList.size();i++)
	{
		iter = mapParentIDList.find(vecDeviceList[i].DeviceID);
		if (iter != mapParentIDList.end())
		{
			iter->second = vecDeviceList[i].level + 1;
            for (int j = 0;j < vecDeviceList.size();j++)
            {
				if (0 == strncmp(vecDeviceList[j].ParentID.c_str(), 
                    iter->first.c_str(), iter->first.length()))
				{
					vecDeviceList[j].level = iter->second;
				}
            }
		}
	}

	for (int i = 0;i < vecDeviceList.size();i++)
	{
		printf("%d %s %s\n", vecDeviceList[i].level,
			vecDeviceList[i].ParentID.c_str(),
			vecDeviceList[i].DeviceID.c_str());
	}

	printf("---------------------------------------\n");
	
	int ntemp = 0;
	string temp = "";
	for (int i = 0;i < vecDeviceList.size();i++)
	{
		if (vecDeviceList[i].level == 0)
		{
			int nCount = ntemp;
			do
			{
				temp = temp + " ";
			} while (nCount--);

			if (ntemp == 0)
			{
				printf("%d %s\n  %s%s\n", vecDeviceList[i].level,
					vecDeviceList[i].ParentID.c_str(), temp.c_str(),
					vecDeviceList[i].DeviceID.c_str());
			}
			else
			{
				printf("%d%s%s\n", vecDeviceList[i].level,
					temp.c_str(),
					vecDeviceList[i].DeviceID.c_str());
			}
			ntemp++;
		}
	}

#if 0

    set<string> setDeviceList;
    for (int i = 0;i < vecDeviceList.size();i++)
    {
        setDeviceList.insert(vecDeviceList[i].ParentID);
        setDeviceList.insert(vecDeviceList[i].DeviceID);
    }
    
    bool bflag = true;
	for (int i = 0;i < vecDeviceList.size();i++)
	{
		for (int j = 0;j < vecDeviceList.size();j++)
		{
            if (0 == strncmp(vecDeviceList[i].ParentID.c_str(), vecDeviceList[j].DeviceID.c_str(), vecDeviceList[i].ParentID.length()))
            {
                //出现在了子目录，所以不是根目录

                bflag = false;
                break;
            }
		}
        if (bflag)
        {
            //未出现在子目录，是根目录
            vecDeviceList[i].level++;
        }
	}

    for (int i = 0;i < vecDeviceList.size();i++)
    {
        printf("%d %s %s\n", vecDeviceList[i].level, 
            vecDeviceList[i].ParentID.c_str(), 
            vecDeviceList[i].DeviceID.c_str());
    }

	printf("\n");

	bflag = true;
	int nlevel = 0;
    int nCount = setDeviceList.size();
    while (nCount--)
    {
		for (int i = 0;i < vecDeviceList.size();i++)
		{
			if (vecDeviceList[i].level < nlevel)
			{
				for (int j = 0;j < vecDeviceList.size();j++)
				{
					if (0 == strncmp(vecDeviceList[i].ParentID.c_str(), vecDeviceList[j].DeviceID.c_str(), vecDeviceList[i].ParentID.length()))
					{
						vecDeviceList[j].level = nlevel;
					}
				}
			}
		}
        nlevel++;
    }


	for (int i = 0;i < vecDeviceList.size();i++)
	{
		printf("%d %s %s\n", vecDeviceList[i].level,
			vecDeviceList[i].ParentID.c_str(),
			vecDeviceList[i].DeviceID.c_str());
	}
#endif
}

